Stable trace automata vs. full trace automata
Identifieur interne : 002095 ( Main/Exploration ); précédent : 002094; suivant : 002096Stable trace automata vs. full trace automata
Auteurs : Vincent Schmitt [France]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 1998.
Abstract
Trace automata provide a well-studied model for systems with concurrent behavior, which is usually given by associated domains of finite or infinite computation systems. Several authors in the literature have characterized order-theoretically these domains which are typically particular Scott domains. In most of these investigations, the question remain open when such a domain can be obtained from some finite automaton. In this paper it is shown that finite stable trace automata and finite full trace automata give rise to the same class of coherent dI-domains. The proof of this result involves combinatorial means from graph theory (colorings) and Ramsey's theorem.
Url:
DOI: 10.1016/S0304-3975(97)00299-5
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003470
- to stream Istex, to step Curation: 003215
- to stream Istex, to step Checkpoint: 001599
- to stream Main, to step Merge: 002212
- to stream Main, to step Curation: 002095
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Stable trace automata vs. full trace automata</title><author><name sortKey="Schmitt, Vincent" sort="Schmitt, Vincent" uniqKey="Schmitt V" first="Vincent" last="Schmitt">Vincent Schmitt</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:8E8F93929B663AF87939EA0A8217C023CBAC440D</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1016/S0304-3975(97)00299-5</idno><idno type="url">https://api.istex.fr/document/8E8F93929B663AF87939EA0A8217C023CBAC440D/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">003470</idno><idno type="wicri:Area/Istex/Curation">003215</idno><idno type="wicri:Area/Istex/Checkpoint">001599</idno><idno type="wicri:doubleKey">0304-3975:1998:Schmitt V:stable:trace:automata</idno><idno type="wicri:Area/Main/Merge">002212</idno><idno type="wicri:Area/Main/Curation">002095</idno><idno type="wicri:Area/Main/Exploration">002095</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Stable trace automata vs. full trace automata</title><author><name sortKey="Schmitt, Vincent" sort="Schmitt, Vincent" uniqKey="Schmitt V" first="Vincent" last="Schmitt">Vincent Schmitt</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>IRISA-IFSIC, Campus de Beaulieu, 35042 Rennes</wicri:regionArea><placeName><region type="region" nuts="2">Région Bretagne</region><settlement type="city">Rennes</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1998">1998</date><biblScope unit="volume">200</biblScope><biblScope unit="issue">1–2</biblScope><biblScope unit="page" from="45">45</biblScope><biblScope unit="page" to="100">100</biblScope></imprint><idno type="ISSN">0304-3975</idno></series><idno type="istex">8E8F93929B663AF87939EA0A8217C023CBAC440D</idno><idno type="DOI">10.1016/S0304-3975(97)00299-5</idno><idno type="PII">S0304-3975(97)00299-5</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Trace automata provide a well-studied model for systems with concurrent behavior, which is usually given by associated domains of finite or infinite computation systems. Several authors in the literature have characterized order-theoretically these domains which are typically particular Scott domains. In most of these investigations, the question remain open when such a domain can be obtained from some finite automaton. In this paper it is shown that finite stable trace automata and finite full trace automata give rise to the same class of coherent dI-domains. The proof of this result involves combinatorial means from graph theory (colorings) and Ramsey's theorem.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Région Bretagne</li></region><settlement><li>Rennes</li></settlement></list><tree><country name="France"><region name="Région Bretagne"><name sortKey="Schmitt, Vincent" sort="Schmitt, Vincent" uniqKey="Schmitt V" first="Vincent" last="Schmitt">Vincent Schmitt</name></region><name sortKey="Schmitt, Vincent" sort="Schmitt, Vincent" uniqKey="Schmitt V" first="Vincent" last="Schmitt">Vincent Schmitt</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002095 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002095 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:8E8F93929B663AF87939EA0A8217C023CBAC440D
|texte= Stable trace automata vs. full trace automata
}}
| This area was generated with Dilib version V0.6.32. |  |